package com.julius.design.suanfa.linked;

import java.util.HashMap;
import java.util.Map;

/**
 * @author julius
 * @date 2021-10-20 下午 3:55
 * <p>
 *        复制一个复杂链表  中等难度
 *        这个算法利用回溯算法（递归）进行解决，主要是
 * </p>
 */
public class CopyRandomLinked {

    /**
     * 缓存，已经拷贝的节点
     */
    private static Map<Node,Node> nodeCache = new HashMap<>();

    public static Node copyRandomList(Node head) {
        //临界条件
        if(head == null){
            return null;
        }
        if(!nodeCache.containsKey(head)){
            Node nodeNew = new Node(head.val);
            nodeCache.put(head,nodeNew);
            //递归拷贝next节点，如果next节点还未创建，则会创建next节点
            nodeNew.next = copyRandomList(head.next);
            //递归拷贝random节点，如果random节点还未创建，则会创建random节点
            nodeNew.random = copyRandomList(head.random);
        }
        return nodeCache.get(head);

    }

    public static class Node{
        int val;

        Node next;

        Node random;

        Node(int val){
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

}
